This invention pertains to a digital electronic system for halftone printing and, more particularly, to a system for generating halftone dots using pointers to address a Look-Up-Table to determine the status (on or off) of individual write spots.
Halftone printing is a printing method whereby printed dots of different size per unit area are used to create a visual effect that simulates continuous tone gradations. All the dots in halftone printing have substantially the same printed optical density. It is the change in their individual size that changes the apparent optical density of an area. The human eye integrates the printed and not printed portions, and perceives that the overall tone gradation in that area changes continuously. True halftone reproduction employs dot patterns of different size dots placed on center lines of a preselected frequency. Other forms of halftone reproduction are also known, which employ dots of a fixed size but in different concentrations per fixed unit area to achieve varying optical densities. However for purposes of generalization, such methods may be viewed as comprising halftone dots of appropriate size along fixed centers, by defining the halftone dot to co-extend with the fixed unit area. Halftone printing has been extremely successful in providing inexpensive high-quality reproductions, both black and white (monochrome) and multicolored, of continuous tone images.
Halftone printing is not without problems, particularly in the reproduction of multicolored images where the complete color spectrum is reproduced using three, four, or even more fundamental colors printed sequentially and in superposed manner. For the final product to accurately reproduce the intended hues, the various dots for each color must be printed substantially over each other. Furthermore, if the pattern of dots is slightly shifted between one or more of the individual colors, moire patterns appear across the print. One solution is to print the various colors using plates on which the dot patterns are absolutely parallel and exactly aligned. These conditions are impractical to maintain in real life. Instead, it was discovered that hues can be maintained, and moire patterns eliminated, if the dots on the plates used for the different colors are placed on centers that form certain predetermined angles relative to each other. It has been found through trial and error that, for optimum results, the desired angles are .+-.15, 30, 45, and 60 degrees. Other orientations may of course be used if they are found to produce acceptable results. Even when monochrome reproductions are involved, the image appearance is improved when the dot centers are aligned at an angle rather than along one edge of the printed page and at 90 degrees thereof.
In traditional printing, the angled halftones are achieved by rotating the screens, used to produce the halftones, an appropriate amount during the exposure stage of a photosensitive film sheet, which then becomes the color separation transparency used to generate a printing plate. Any conceivable angle can be reproduced with minimal effort. With the advent of computers and electronic scanners which are used to read a continuous tone image and generate a set of digital data representing the three, four or whatever number of fundamental colors used in a specific application, the physical embodiment of the image has disappeared. The images that generate the color separations are electronic images maintained as a compilation of digital signals in a computer memory. The halftone color separation transparencies are produced by directly exposing a photosensitive film using data from a computer to drive a printer. Sometimes even this step is omitted and the printing plate is produced directly using computer-controlled, high-powered laser printers, thereby completely eliminating the need for a tangible color separation transparency. In order to produce a successful product, electronic equipment and/or software attempting to replace traditional techniques, must recreate the same image as would be produced using traditional screening processes. This includes generating halftone dots laid out on centers that are angled along similar angles as they would be had they been created by physically placing the screens over a photosensitive film at an angle and exposing the film therethrough.
In electronic printing, a continuous tone image is usually scanned with a scanner having a given resolution along two orthogonal directions substantially parallel to the image edges, assuming that the image is contained in a parallelogram, as is the usual case. The scanner output is recorded in digital format typically using an 8 bit system to produce a collection of numbers varying between 0 and 255, indicative of the apparent density of individual picture elements (PELs) representing the image. If the image is in color, filters are used to obtain multiple sets of data, each representing a fundamental color used in printing, such as cyan, magenta, yellow, and, in four color printing instances, black. Because the same treatment is applied to all colors in the halftone generation process, each color will be treated henceforth as a monochrome without regard to whether it is part of a multicolor system. Only the specific angle chosen for each color separation transparency changes. The accumulated data may undergo a number of alterations and modifications as part of electronic image processing; these alterations are of no import to this invention and depend on the sophistication of the work station in which they are effected, and the needs of the particular application. They may include color shifts, image blending, addition or deletion of text, etc. Following any such electronic data manipulation, the data are sent to a printer for the generation of the output. The output is a monochrome halftone representation of the image as subsequently modified.
Output printers almost always have substantially higher resolution capabilities than the input scanner. Thus, output laser printers may write with a resolution of 4,800 spots per inch, while read scanners may read and digitize data at resolutions such as 300 PELs per inch. As a result, there will typically be a number of fractional halftone dots included in each elemental area corresponding to the original continuous tone image. Furthermore, depending on the desired printing quality output, the color separation dots will be arranged on center lines at a spacing typically selected from 85, 100, 120, 133, 150 or 175 lines per inch; other frequencies may of course be used. In a system where the halftone dots are at 0.degree. with a dot centerline spacing of 100 lines per inch and the writing resolution of the printer is 4,800 spots per inch, each dot will be constructed with a maximum of 48.times.48=2,304 spots, assuming that the printer affords equal resolution in both horizontal and vertical scan directions. Those 2,304 spots are available to generate any predetermined dot shape for any one of a maximum of 2,305 distinct density levels, to duplicate the density level of the original image (PELS) at that location. The total of these spots which may be used to create a dot will be referred to hereafter as a dot template. Thus, each dot template in this example consists of 2,304 spots.
In most printers, the write spot travels across a generally rectangular writing surface along a path substantially parallel to one edge of the surface. The surface is also advanced between lines in an orthogonal direction so as to produce an orthogonal raster pattern aligned with the surface edges. In order to more closely reproduce the traditional printing angles, in electronic halftone reproduction, it has been found advantageous to align the dot centers along center lines whose angle with the raster direction forms an angle that has a rational tangent. For instance, instead of 15 degrees, one would select 14.931 degrees; this is an angle whose tangent is 4/15. U.S. Pat. No. 3,657,472 discusses the rational tangent angle concept and associated advantages in detail, and to the extent needed in this case, its teachings are incorporated herein. Since the dot templates are aligned at an angle to the raster scan, the write spot which travels along the raster scan line, enters and exits each dot template at different points relative to the template itself. To determine the on or off status of the spot at each location, the prior art teaches two different approaches.
The first approach is based on defining a fundamental tile comprising a number of dot templates and partial dot templates. The image area is then divided into a multiplicity of fundamental tiles completely covering the image surface. The fundamental tile includes the minimum area that must be encompassed so that as the writing spot advances along a scan line, the spot always enters each tile at the same relative point, i.e., the pattern repeats. In the case of a 90 degree orientation, the fundamental tile comprises only one dot template consisting of the spots that are included in one halftone dot area. The scanning write spot always enters the dot template in the same relative location along each scan line. The on or off status of the spot may then be ascertained with reference to a Look-Up-Table (LUT) which, in the example of the 48.times.48 spots, is comprised of 2,034 values, one for each spot position within the tile.
In the case where the dot centers form an angle with the raster, the fundamental tile will consist of a larger area which will comprise a number of dot templates and partial dot templates which must be included to obtain a repeating pattern. Thus, a much larger look up table is needed to provide reference values for the spot status within the fundamental tile. For example, FIG. 2 shows a portion of a halftone print-out comprising dot templates, each consisting of 52 write spots, arranged in a pattern with center lines making an angle .theta. of 56.31 degrees with the scan line. The repeating tile pattern is outlined in FIG. 2, and encompasses 5 full dot templates and 16 partial dot templates extending over an area of 26.times.26 write spots. As a result, an LUT consisting of 676 values must be used to determine the spot status at each location within the tile. The number of LUT values needed for FIG. 2 is 13 times higher than the number of LUT values needed for a single dot template. In the case where the angle .theta. is about 30 degrees, a popular selection in the graphic arts, the stored data are one thousand, two hundred and eighty five times (1,285) larger than for a single dot. For a dot template consisting of 2,304 spots, the fundamental tile would require 29,952 and 2,960,640 values for .theta.=56.31 degrees and .theta.=30 degrees, respectively.
The second approach uses an algorithm to calculate the relative position of the spot within a fundamental dot tile and, thus, avoids such large Look-Up-Tables. In this case, a dot template is used which is oriented along the axes of a coordinate system defined by the angled dot centerlines. For each position along the scan line, a calculation (coordinate transform followed by modulo calculations) is performed to find where a spot is located in the angled dot template. The status of the spot is next determined with reference to a LUT which includes comparison values for all the spot locations within a single dot template. In the case of the 52 spot dot template of FIG. 2, the Look-Up-Table would only have 52 values. However, before the Look-Up-Table could be accessed, the address of the spot needs to be calculated.
Both approaches have limitations. As the angles change, the first approach can require exceedingly large amounts of memory to store the tile data. The second approach requires calculating circuitry and needs time to perform the calculation for each point. Neither approach presents a satisfactory solution for the electronic generation of angled halftones in a manner which is fast, inexpensive, and provides good flexibility in choosing different dot centerline angles.
It is an object of the present invention to provide a system for determining the status of a raster's write spot in an output device for the generation of halftone dots, which system does not use mathematical operations while at the same time limits the size of LUTs and the amount of data stored therein.